package org.ayachinene.leetcode.problems;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P17 {

    static class Solution {

        private static final Map<Character, List<String>> M = new HashMap<>(8);
        static {
            M.put('2', List.of("a", "b", "c"));
            M.put('3', List.of("d", "e", "f"));
            M.put('4', List.of("g", "h", "i"));
            M.put('5', List.of("j", "k", "l"));
            M.put('6', List.of("m", "n", "o"));
            M.put('7', List.of("p", "q", "r", "s"));
            M.put('8', List.of("t", "u", "v"));
            M.put('9', List.of("w", "x", "y", "z"));
        }

        public List<String> letterCombinations(String digits) {
            return letterCombinations(digits.toCharArray(), 0, digits.length());
        }

        /** 返回digits[l..r)的字母组合
         * 例：
         * digits = "234"
         * digits[0..2)即"23"
         * 则letterCombinations(digits, 0, 2)返回"23"的字母组合
         * 为：["ad","ae","af",
         *     "bd","be","bf",
         *     "cd","ce","cf"]
         */
        private List<String> letterCombinations(char[] digits, int l, int r) {
            if (digits.length == 0) {
                return new ArrayList<>();
            }

            if (l >= r) {
                return new ArrayList<>();
            }

            if (r - l == 1) {
                return M.get(digits[l]);
            }

            List<String> preCombinations = letterCombinations(digits, l, r - 1);

            List<String> combinations = new ArrayList<>();
            preCombinations.forEach(preComb -> {
                M.get(digits[r - 1]).forEach(letter -> {
                    combinations.add(preComb + letter);
                });
            });

            return combinations;
        }
    }
}
